package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;

/**
 * AC
 */
class Solution98 {
    public boolean isValidBST(TreeNode root) {
        // 根节点为空
        if (root == null) {
            return true;
        }

        // 左右子树都为空
        if (root.left == null && root.right == null) {
            return true;
        }

        // 左子树为空，右子树不为空
        if (root.left == null) {
            if (TreeUtils.isAllMoreThanVal(root.right, root.val) && isValidBST(root.right)) {
                return true;
            }
            return false;
        }

        // 右子树为空，左子树不为空
        if (root.right == null) {
            if (TreeUtils.isAllLessThanVal(root.left, root.val) && isValidBST(root.left)) {
                return true;
            }
            return false;
        }

        // 左右子树都不为空
        if (TreeUtils.isAllLessThanVal(root.left, root.val) && TreeUtils.isAllMoreThanVal(root.right, root.val) && isValidBST(root.left) && isValidBST(root.right)) {
            return true;
        }

        return false;
    }

}

/**
 * 98. 验证二叉搜索树
 */
public class leetcode98 {


    public static void main(String[] args) {
        Solution98 solution98 = new Solution98();

        TreeNode root = generateTestData();

        boolean result = solution98.isValidBST(root);

        System.out.println(result);

    }

    private static TreeNode generateTestData() {

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        return root;
    }


}
